package com.lfc.stackandqueue;

import java.util.*;

/**
 * 栈和队列测试用例
 */
public class Test1 {
    public static void main(String[] args) {
//        method01();
//        method02();
//        int[] arr = {2, 3, 1, 0, 3};
//        int idx = 0;
//        for (int i : arr) idx ^= i;
//        System.out.println(idx);
//        method06();
        method08();
//        method10();
//        Map<String,String> map=new HashMap<>();


    }

    private static void method01() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        node1.next = node2;
        node2.next = node3;
        int[] ints = reversePrint(node1);
        System.out.println(Arrays.toString(ints));

    }

    /**
     * 从尾打印链表，解决方式，使用栈的方式解决
     *
     * @param head
     * @return
     */
    private static int[] reversePrint(ListNode head) {
        // 第一种是采用栈的方式解决
//        Stack<ListNode> stack=new Stack<>();
//        ListNode listNode = head;
//        while (head!=null){
//            stack.push(listNode);
//            listNode=listNode.next;
//        }
//        // 使用数字遍历
//        int[] ints = new int[stack.size()];
//        for (int i = 0; i < ints.length; i++) ints[i]=stack.pop().val;
//        return ints;
        // 第二种是采用标记法的方式解决
        int sum = 0;
        ListNode listNode = head;
        while (listNode != null) {
            sum++;
            listNode = listNode.next;
        }

        int[] arrs = new int[sum];
        int idx = sum - 1;
        while (head != null) {
            arrs[idx--] = head.val;
            head = head.next;
        }
        return arrs;
    }

    private static void method02() {
        int[] pushed = {1, 2, 3, 4, 5}, poped = {4, 5, 3, 2, 1};
        System.out.println(validateStackSequences(pushed, poped));
    }

    public static boolean validateStackSequences(int[] pushed, int[] poped) {
//        Stack<Integer> stack=new Stack<>();
//        for (int i = 0; i < pushed.length; i++) {
//            stack.push(pushed[i]);
//            while (!stack.isEmpty() && stack.peek()==poped[i]){
//                stack.pop();
//                i++;
//            }
//        }
//        return stack.isEmpty();
        int l = 0, r = 0;
        for (int i = 0; i < pushed.length; i++) {
            pushed[l] = pushed[i];
            while (l >= 0 && pushed[l] == poped[r]) {
                l--;
                r++;
            }
            l++;
        }
        return l == 0;
    }

    public char firstUniqChar(String s) {
        int[] dp = new int[26];
        for (char c : s.toCharArray()) {
            dp[c - 'a']++;
        }
        for (char c : s.toCharArray()) {
            if (dp[c - 'a'] == 1) {
                return c;
            }
        }
        return ' ';
    }

    public ListNode deleteNode(ListNode head, int val) {
        // 定义一个哨兵节点
        ListNode h = new ListNode(-1);
        // 使用哨兵的下一个节点指向头节点
        h.next = head;
        // 定义两个节点，分别指向上一个节点和下一个节点
        ListNode pre = h, tmp = head;
        while (tmp != null) {
            if (tmp.val == val) pre.next = tmp.next;
            // 断开的两个节点在此刻连接起来
            pre = tmp;
            tmp = tmp.next;
        }
        return h.next;
    }

    public static boolean exist(char[][] board, String word) {
        char[] words = word.toCharArray();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, words, i, j, 0)) return true;
            }
        }
        return false;

    }

    public static boolean dfs(char[][] board, char[] word, int i, int j, int k) {
        if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word[k]) return false;
        if (k == word.length - 1) return true;
        char tmp = board[i][j];
        board[i][j] = '/';
        boolean result = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) ||
                dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i, j - 1, k + 1);
        board[i][j] = tmp;
        return result;
    }

    public static void method03() {
        int arr[] = {2, -1, 2};
        int k = 3;
        System.out.println(shortestSubarray(arr, k));
    }

    public static int shortestSubarray(int[] nums, int k) {
        // 计算出相应的前缀和
        int n = nums.length;
        long[] sfd = new long[n + 1];
        for (int i = 0; i < n; i++) sfd[i + 1] = sfd[i] + nums[i];
        int res = n + 1;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            long l = sfd[i];
            while (!queue.isEmpty() && (l - sfd[queue.peekFirst()]) >= k) {
                res = Math.min(res, i - queue.pollFirst());
            }
            while (!queue.isEmpty() && sfd[queue.peekLast()] >= l) queue.pollLast();
            queue.offerLast(i);
        }
        return res < n + 1 ? res : -1;
    }

    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> list = new ArrayList<>();
        for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                list.add(nums1[i]);
                j++;
                i++;
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) res[i] = list.get(i);
        return res;
    }

    public static int[][] matrixReshape(int[][] mat, int r, int c) {
        int matr = mat.length;
        int matc = mat[0].length;
        int count = matr * matc;
        if (matc == c && matr == r || count != r * c) return mat;
        int[][] res = new int[r][c];
        for (int i = 0; i < count; i++) {
            res[i / c][i % c] = mat[i / matc][i % matc];
        }
        return res;
    }

    public List<List<Integer>> generate(int numRows) {
        // 记录结果值
        List<List<Integer>> res = new ArrayList<>();
        // 记录每一行的元素
        List<Integer> row = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            // 下面的每行元素都会比上一行元素多一个元素，给第一个位置加1
            row.add(0, 1);
            // 遍历每一行的结果，遍历的时候跳过第一个和最后一个，
            // 每个格子的值都是他正上和左上角的元素的和
            for (int j = 1; j < row.size() - 1; j++) {
                row.set(j, row.get(j) + row.get(j + 1));
            }
            // 把结果放入到res中
            res.add(new ArrayList<>(row));
        }
        return res;

    }

    public static void method06() {
        int nums[] = {1, 2, 3, 4, 5};
        int target[] = {2, 3, 4, 6, 7, 8};
        f(nums, target);
    }

    public static long makeSimilar(int[] nums, int[] target) {
        f(nums, target);
        long ans = 0L;
        for (int i = 0; i < nums.length; ++i)
            ans += Math.abs(nums[i] - target[i]);
        return ans / 4;
    }

    private static void f(int[] a, int[] b) {
        // 由于元素都是正数，把奇数变成相反数，这样排序后奇偶就自动分开了
        for (int i = 0; i < a.length; ++i) if ((a[i] & 1) == 1) a[i] = -a[i];
        Arrays.sort(a);
        for (int i = 0; i < b.length; ++i) if ((b[i] & 1) == 1) b[i] = -b[i];
        Arrays.sort(b);
    }

    private static void method08() {
        int[][] matrix = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(maxValue(matrix));
    }

    public static int maxValue(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;
        int[][] dp = new int[row + 1][col + 1];
        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + mat[i - 1][j - 1];
            }
        }
        return dp[row][col];
    }

    private static void method10() {
        int[] arr = {11, 81, 94, 43, 3};
        System.out.println(sumSubarrayMins(arr));
    }

    public static int sumSubarrayMins(int[] arr) {
        // 使用动态规划的方式
        int n = arr.length;
        long res = 0l;
        int mod = (int) 1e7;
        int[] dp = new int[n];
        Deque<Integer> statck = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            while (!statck.isEmpty() && arr[statck.peek()] > arr[i]) statck.pop();
            int k = statck.isEmpty() ? i + 1 : i - statck.peek();
            dp[i] = k * arr[i] + (statck.isEmpty() ? 0 : dp[i - k]);
            res = (res + dp[i]) % mod;
            statck.push(i);
        }
        return (int) res;
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        int res = 1;
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[i] > dp[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

}
